package mo.leetcode_top;

import mo.common.TreeNode;

public class L105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    private TreeNode build(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight) {
        if (pLeft > pRight || iLeft > iRight) {
            return null;
        }
        int val = preorder[pLeft];
        int i = 0;
        for (; i <= iRight; i++) {
            if (inorder[i] == val) {
                break;
            }
        }
        TreeNode root = new TreeNode(val);
        root.left = build(preorder, pLeft+1, pLeft+i-iLeft, inorder, iLeft, i-1);
        root.right = build(preorder, pLeft+i-iLeft+1, pRight, inorder, i+1, iRight);
        return root;
    }

    public static void main(String[] args) {
        L105 test = new L105();
        TreeNode treeNode = test.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(treeNode);
    }

}
